package com.wang.sort;

public class Demo11_StackAndQueue {
    public static class Node<T>{
        public T value;
        public Node<T> pre;
        public Node<T> next;

        public Node(T data){
            value = data;
        }
    }
    public static class DoubleEndsQueue<T>{
        public Node<T> head;
        public Node<T> tail;
        //从队列头部添加
        public void addFromHead(T value){
            Node<T> cur = new Node<>(value);
            if(head == null){
                head = cur;
                tail = cur;
            }
            else {
                cur.next = head;
                head.pre = cur;
                head = cur;
            }
        }
        //从队列尾部添加
        public void addFromBottom(T value) {
            Node<T> cur = new Node<>(value);
            if(head == null){
                head = cur;
                tail = cur;
            }
            else {
                cur.pre = tail;
                tail.next = cur;
                tail =cur;
            }
        }
        //从头部删除节点
        public T popFromHead(){
             if(head == null){
                 return null;
             }
             Node<T> cur = head;
             if(head == tail){
                head = tail = null;
             }
             else {
                 head = head.next;
                 cur.next = null;
                 head.pre = null;
             }
             return cur.value;
        }
        //从尾部删除
        public T popFromBottom(){
            if (head == null){
                return null;
            }
            Node<T> cur = tail;
            if(head == tail){
                head = tail = null;
            }
            else {
                tail = tail.pre;
                tail.next = null;
                cur.pre = null;
            }
            return cur.value;
        }
        public boolean isEmpty(){
            return head == null;
        }
        public static class MyStack<T> {
            private DoubleEndsQueue<T> queue;
            public MyStack() {
                queue = new DoubleEndsQueue<T>();
            }
            public void push(T value) {
                queue.addFromHead(value);
            }
            public void pop() {
                queue.popFromHead();
            }
            public boolean isEmpty(){
                return queue.isEmpty();
            }
        }
        public static class MyQueue<T> {
            private DoubleEndsQueue<T> queue;

            public MyQueue() {
                queue = new DoubleEndsQueue<T>();
            }
            public void push(T value) {
                queue.addFromHead(value);
            }
            public void poll() {
                queue.popFromBottom();
            }
            public boolean isEmpty(){
                return queue.isEmpty();
            }

        }


    }


}
